package Algorithm.set;

import java.util.Scanner;

//并查集
public class Union_Find_Set {
    int n;
    int m;
    int[] f;
    int num=0;
    Union_Find_Set(int n,int m){
        this.n = n;
        this.m = m;
    }
    public void Scan(){
        Scanner s = new Scanner(System.in);
        if(s.hasNextInt()){
            n = s.nextInt();
        }
        if (s.hasNextInt()){
            m = s.nextInt();
        }
        System.out.println(n+" "+m);
        /*并查集的初始化*/
        num = n;
        f = new int[n+1];
        for(int i=0;i<=n;i++ ){
            f[i] = i;
        }
        int t1=0,t2=0;
        for(int i =0;i<m;i++){
            char ch='e';
            if(s.hasNextInt()){
                t1 = s.nextInt();
            }
            if(s.hasNextInt()){
                t2 = s.nextInt();
            }
            if (s.hasNext()){
                ch = s.next().charAt(0);
            }
            System.out.println(t1+" "+t2+" "+ ch);
            if(ch=='f'){
                merge(t1,t2);
            }
        }
    }
    public void merge(int v1 ,int v2){  //合并两子集
        int t1 = getf(v1);
        int t2 = getf(v2);
        if(t1 !=t2){
            f[t2] = t1;
            num--;
        }
    }
    public int getf(int v){              //路径压缩+寻找父亲结点
        if(f[v] == v){
            return v;
        }else{
            f[v] = getf(f[v]);
            return f[v];
        }
    }

    public static void main(String[] args) {
        Union_Find_Set ufs = new Union_Find_Set(11,10);
        ufs.Scan();
        System.out.print("团伙数量"+ufs.num);
    }

}
/*
测试数据
11 11
1 2 f
3 4 f
5 2 f
4 6 f
2 6 f
7 11 f
8 7 f
9 7 f
9 11 f
1 6 f
2 3 e
*/